Extremely complex geometric databases offer a variety of interesting challenges for visibility algorithms. Consider the problem, for example, of enabling an interactive walk-through of a detailed geometric database describing an entire city, complete with trees and flowers, buildings, the furniture inside the buildings and the contents of the furniture. Traditional visibility algorithms running on currently available hardware cannot come close to dealing with this complexity and it will be a long time before faster hardware alone will suffice. In order to get the most out of the available hardware, it would be advantageous to exploit properties of the visibility computation itself to develop faster algorithms.
There are at least three types of coherence inherent in the visibility computation which can be exploited to accelerate a visibility algorithm. The first is object-space coherence: in many cases a single computation can resolve the visibility of a collection of objects which are near each other in space. The second is image-space coherence: in many cases a single computation can resolve the visibility of a collection of pixels simultaneously. The third is temporal coherence: knowing the visibility of a collection of objects in one frame can often be used to accelerate visibility computation for the objects in the next frame.
There have been many attempts to accelerate traditional ray-tracing and Z-buffering techniques. Each of these attempts exploits some aspect of the coherence inherent in the visibility computation itself. None of them, however, simultaneously exploits object-space, image-space and temporal coherence.
Visibility algorithms are discussed generally in Foley, Van Dam, Feiner and Hughes, "Computer Graphics, Principles and Practice" (1990), Chap. 15, incorporated herein by reference. The dominant algorithms in use today for visibility computations are Z-buffer scan conversion and ray-tracing. Since Z-buffers do not handle partially transparent surfaces well, comparisons with Z-buffer techniques are best made with models consisting entirely of opaque surfaces. For these models, only rays from the eye to the first surface are relevant for visibility, so the choice is between Z-buffering and ray-casting (ray-tracing with no secondary rays).
The ray-tracing literature abounds with references to object-space coherence. A variety of spatial subdivisions have been used to exploit this coherence. See, for example, S. M. Rubin and T. Whirred, "A 3-dimensional representation for fast rendering of complex scenes," Computer Graphics, vol. 14, no. 3, pp. 110-116, July 1980; A. Glassner, "Space subdivision for fast ray tracing," IEEE CG&A, vol. 4, no. 10, pp. 15-22 (October 1984); D. Jevans and B. Wyvill, "Adaptive voxel subdivision for ray tracing," Proc. Graphics Interface '89, pp. 164-172, June 1989; T. Kay and J. Kajiya, "Ray tracing complex scenes," Computer Graphics, vol. 20, no. 4, pp. 269-278, August 1986; and Michael R. Kaplan, "The use of spatial coherence in ray tracing," in Techniques for computer graphics, etc. D. Rogers and R. A. Earnshaw, Springer-Verlag, New York, 1987, all of which are incorporated herein by reference.
Temporal coherence is much less commonly exploited in practice, but various techniques exist for special cases. For example, if all the objects are convex and remain stationary while the camera moves, then there are constraints on the way visibility can change (H. Hubschman and S. W. Zucker, "Frame to frame coherence and the hidden surface computation: constraints for a convex world," ACM TOG, vol. 1, no. 2, pp. 129-162, April, 1982, incorporated herein by reference) which a ray tracer might exploit. On the other hand, if the camera is stationary, then rays which are unaffected by the object motion can be detected and used from the previous frame. See, for example, David Jevans, "Object space temporal coherence for ray tracing," Proc. Graphics Interface, '92 Vancouver, B.C., pp. 176-183, May 11-15, 1992, incorporated herein by reference.
When interactivity is not an issue and sufficient memory is available, it can be feasible to render an entire animation sequence at once using spacetime bounding boxes. See, for example, A. Glassner, "Spacetime ray tracing for animation," IEEE CG&A, vol. 4, no. 10, pp. 15-22, October 1984, and J. Chapman, T. W. Calvert, and J. Dill, "Exploiting temporal coherence in ray tracing," Proceedings of Graphics Interface '90, pp. 196-204, 1990, both incorporated herein by reference.
While these techniques make good use of object-space coherence and sometimes exploit temporal coherence effectively, they unfortunately make little or no use of image-space coherence since each pixel is traced independently from its neighbors. There are heuristic methods which construct estimates of the results of ray-tracing a pixel from the results at nearby pixels (e.g. Sig Badt, Jr., "Two algorithms for taking advantage of temporal coherence in ray tracing," The Visual Computer, no. 4, pp. 123-132, 1988, incorporated herein by reference, but there seems to be no guaranteed algorithm which makes good use of image-space coherence in ray tracing.
With Z-buffer methods (and scan conversion methods in general) the problems are very different. Ordinary Z-buffer rendering is usually implemented with an initial set-up computation for each primitive followed by a scan-conversion phase in which the affected pixels are incrementally updated. This already makes very good use of image-space coherence, so the remaining challenge with Z-buffer methods is to exploit object-space and temporal coherence effectively.
A simple method of using some object-space coherence in Z-buffer rendering is to use a spatial subdivision to cull the model to the viewing frustum. See B. Garlick, D. Baum and J. Winger, "Interactive viewing of large geometric databases using multiprocessor graphics workstations," Siggraph '90 Course Notes (Parallel Algorithms and Architectures for 3D Image Generation), 1990, incorporated herein by reference. While this can provide substantial speed-ups, it exploits only a small portion of the object-space coherence in models with high depth complexity. In architectural models, for example, a great deal of geometry is often hidden behind walls yet lies within the viewing frustum.
In order to make use of more of the object-space coherence in architectural models, certain authors have proposed dividing models up into a set of disjoint cells and precomputing the potentially visible set (PVS) of polygons from each cell. See John Airey, "Increasing Update Rates in the Building Walkthrough System with Automatic Model--Space Subdivision and Potentially Visible Set Calculations," Technical Report TR90-027, The University of North Carolina at Chapel Hill, Department of Computer Science (1990); John Airey, John Rohlf, and F. Brooks. "Towards image realism with interactive update rates in complex virtual building environments," ACM SIGGRAPH Special Issue on 1990 Symposium on Interactive 3D Graphics, 24 (2) pp. 41-50, 1990; S. Teller and C. Sequin, "Visibility Preprocessing for Interactive Walkthroughs," Computer Graphics '91 (Proc. SIGGRAPH '91), 25 (4) pp. 61-69 (1991); and S. Teller and C. Sequin, "Visibility computations in polyhedral three-dimensional environments," U.C. Berkeley Report No. UCB/CSD 92/680, April 1992, all incorporated herein by reference. In order to render an image from any viewpoint within a cell, only the polygons in the PVS need be considered. These PVS schemes attempt to make good use of both object-space and image-space coherence. Nonetheless, they suffer from some important limitations. Before they can be used at all, they require an expensive precomputation step to determine the PVS and a great deal of memory to store it. Teller and Sequin, for example, report over 6 hours of precomputation time on a 50 MIP machine to calculate 58 Mb of PVS data needed for a model of 250,000 polygons.
Perhaps more importantly, the way these methods make use of cells may limit their appropriateness to architectural models. In order to achieve maximum acceleration, the cells must be 3D regions of space which are almost entirely enclosed by occluding surfaces so most cells are hidden from most other cells. For architectural models, this often works well since the cells can be rooms, but for outdoor scenes and more general settings, it is unclear whether or not PVS methods will be effective. In addition, the currently implemented algorithms make very special use of axially aligned polygons such as flat walls in rectilinear architectural models. While the methods can in principle be extended to use general 3D polygons for occlusion, the necessary algorithms are believed to have much worse computational complexity. Finally, although the implementations prefetch PVS data for nearby cells to avoid long latencies due to paging, they cannot be said to exploit temporal coherence in the visibility computation very effectively.
In Donald Meagher, "Efficient synthetic image generation of arbitrary 3-D objects," Proc. IEEE Conf. on Pattern Recognition and Image Processing, pp. 473-478, June 1982, incorporated herein by reference, a rendering algorithm is described which uses object-space octrees with image-space quadtrees. The algorithm described therein displays the octree itself rather than using it to cull a polygonal database, so that algorithm is directly applicable to volume, rather than surface datasets. Nonetheless this algorithm does make use of both object-space and image-space coherence, though it does not exploit temporal coherence.
Accordingly, there is a great need for a visibility algorithm which can take advantage of all three types of coherence in order to significantly speed up the rendering of 3D scenes.